\section{Introduction}

Inlining represents an important optimization technique in any modern
compiler.  It avoids the overhead of a full function call, and it
allows further optimization in the calling function in the form of
type inference, loop optimizations, and more.

While the advantages of inlining are well known and well documented,
inlining also entails some disadvantages.  It increases the size of
the code, with a possible negative impact on processor cache
performance.  It also increases pressure on register allocation,
possibly making it necessary to spill registers to the stack more
often.  Most importantly, though, as Ayers et al. point out
\cite{Ayers:1997:AI:258915.258928, Ayers:1997:AI:258916.258928}, since
many optimization algorithms do not have linear-time complexity in the
size of the code, inlining can have a serious impact on the execution
time of the compiler.

Some authors distinguish between \emph{procedure integration} and
\emph{inline expansion} \cite{Muchnick:1998:ACD:286076}.  Both
techniques are often referred to with the abbreviated form
\emph{inlining}.  Our use of \emph{inlining} corresponds to
\emph{procedure integration}.

Most literature sources define inlining as ``replacing a call to a
function with a copy of the body of the called function'' (see e.g.,
\cite{Chang:1989:IFE:74818.74840,Chang:1989:IFE:73141.74840,
  Scheifler:1977:AIS:359810.359830}). This definition suggests that
inlining is an all-or-nothing transformation.  In this paper, we
present a technique that allows for \emph{partial} inlining.  More
precisely, it allows for a \emph{prefix} of the callee to be copied
into the caller.  We obtain this property by using \emph{local graph
  rewriting} at the level of instructions in intermediate code.  A
single instruction is inlined in each step, preserving the overall
semantics of the program, and thereby allowing us to stop the process
at any time.

The traditional definition of inlining is too vague for our
purpose.  It suggests that the sole purpose of inlining is to avoid
overhead in the function-call protocol.  However, on modern
processors, this overhead is insignificant.  For the purpose of this
paper, we would also like to avoid the creation of a local
\emph{environment} that would normally be necessary for each
invocation of the callee.  This additional requirement poses
additional restrictions as to when inlining is appropriate.

In this paper, we discuss only the inlining technique itself.  We do
not consider the policy to determine when it is advantageous to
perform the technique, and, although our technique allows for partial
inlining, we also do not consider the policy of when inlining should
stop.

%%  LocalWords:  inlining
